package com.sam.book.tree;

import java.util.Stack;

/**
 * 二叉树
 * Created by samwang on 2017/12/23.
 */
public class BinaryTree {

    public static void main(String[] args) {

        BinaryNode expressionTree = expressionTree();
        expressionInorderTraversal(expressionTree);


    }


    /**
     * @return 构造一棵表达式树
     */
    static BinaryNode expressionTree() {
        char[] input = {'a', 'b', '+', 'c', 'd', 'e', '+', '*', '*'};//(a+b)*(c*(d+e))
        Stack<BinaryNode> queue = new Stack<>();

        for (char c : input) {
            BinaryNode treeNode = new BinaryNode();
            treeNode.element = c;
            if (c == '+' || c == '-' || c == '*' || c == '/') {
                treeNode.right = queue.pop();
                treeNode.left = queue.pop();
            }
            queue.push(treeNode);

        }

        return queue.pop();

    }

    /**
     * @return 表达式树中序遍历
     */
    public static void expressionInorderTraversal(BinaryNode node) {
        if (node.left != null && node.right != null) {
            System.out.print("(");
            expressionInorderTraversal(node.left);
            System.out.print(node);
            expressionInorderTraversal(node.right);
            System.out.print(")");
        } else {
            System.out.print(node);
        }

    }


    static class BinaryNode {
        Object element;
        BinaryNode left;
        BinaryNode right;

        @Override
        public String toString() {
            return element.toString();
        }


    }


}
